package algorithm.t202110;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/27 8:45
 * @description :8道
 * 红尘来去有几轮，醉酒当歌笑俗人。
 * persevere to last
 * 2021.10.27
 */
public class t20211027 {

    //301. 删除无效的括号
    public List<String> removeInvalidParentheses(String s) {
    /*
    我们做BFS，上一层level和下一层level之间的关系为：把所有上一层level中的每个元素都拿出来，
    列举出在删除一个括号后的所有可能的情况。(不管删除以后是否合法），添加到下一个level中的元素。

        例如：current level是 ["(()", "())"]
        - 那么下一层level中的元素应该是:
        1. 对 "(()" 删除一个括号的所有可能为： (), (), ((
        2. 对 "())" 删除一个括号的所有可能为： (), )), ()
        这六个就是下一个level的全部内容了。

     */


        //拿到第一层，
        HashSet<String> currentLevel = new HashSet<>();
        currentLevel.add(s);

        while (true) {
            List<String> collect = currentLevel.stream()
                    .filter(this::isValid1)
                    .collect(Collectors.toList());
            if (collect.size() > 0) {//表示该字符串是一个合法字符串
                return collect;
            }

            //程序走到这说明该字符串的【符号】有问题，那么我们就将 '删除一个括号‘的所有情况都放在nextLevel
            HashSet<String> nextLevel = new HashSet<>();

            for (String item : currentLevel) {//从currentLevel拿到目标字符串

                for (int i = 0; i < item.length(); i++) {

                    //只对括号做判断处理，因为字母数字没有任何影响
                    if (s.charAt(i) == '(' || s.charAt(i) == ')') {
                        //这段逻辑是核心代码。意思是：如果字符串中下标i的元素是'（'或者 '）' 那么就删掉这个 '('或')'
                        //例如：字符串为"() () ()"【空格是方便观察】，现在i为0
                        //那么 本次nextLevel添加的元素就是 "" + ") () ()"，也就是添加了”) () ()"
                        //可以看出 删掉了下标为0的'('
                        nextLevel.add(item.substring(0, i) + item.substring(i + 1));
                    }

                }
            }

            if (currentLevel.size() == 0) {
                //表示这
                return new ArrayList<>();
            } else {
                currentLevel = nextLevel;
            }

        }

    }

    public boolean isValid1(String string) {
        int count = 0;

        for (char c : string.toCharArray()) {
            if (c == '(') {
                count++;
            } else if (c == ')') {
                count--;
            }
            if (count < 0) return false;

        }

        return count == 0;
    }

    //20.有效的括号
    public boolean isValid2(String s) {
        /*
            java中将字符(Char)转换为字符串的四种方式

                方法一:使用字符类Character自带的toString()方法
                例如：char c1='c';
                     String str=Character.toString(c1);

                方法二：使用匿名字符数组形式
                例如： char c1='a';
                       String str=new String(new char[]{c1});
                方法三：使用字符串拼接方式
                 例如： char c1='q';
                        String str=c1+"";
                方法四：使用String的ValueOf()
                 例如： char c1='t';
                        String str=String.ValueOf(c1);
         */

        if (s == null || s.length() == 1) return false;//若为空或者长度为1，直接返回false

        LinkedList<String> stack = new LinkedList<>();//
        HashMap<String, String> map = new HashMap<>();//建立【括号】之间的映射关系

        map.put("(", ")");
        map.put("{", "}");
        map.put("[", "]");

        for (char item : s.toCharArray()) {
            if (item == '(' || item == '{' || item == '[') {//若为左括号，直接入栈不考虑~
                stack.push(new String(new char[]{item}));
            } else {//否则就为右括号，那么要就要进行判断了
                //若此时栈为空，你进来一个右括号，则直接返回false
                if (stack.isEmpty()) return false;
                //若栈不为空，则看看栈顶左括号对应的右括号是否和 当前准备入栈的右括号相同，若相同，将栈顶左括号弹出，继续循环，若不相同直接false
                String value = map.get(stack.peek());
                if (value.equals(Character.toString(item))) {
                    stack.pop();

                } else {
                    return false;
                }

            }

        }
        //最后得要判断一下栈是否为空，为什么呢，假如有一个字符串为"(((((((",那么它就会跳过右括号的判断一直入栈，这样不行，所以如果是一个合法的【符号字符串】，栈一定为空
        return stack.isEmpty() ? true : false;

    }

    //获取字符串中有效括号的个数
    static public int isValid3(String s) {
        if (s == null || s.length() == 1) return 0;

        int count = 0;
        LinkedList<String> stack = new LinkedList<>();

        for (char item : s.toCharArray()) {

            if (item == '(') {
                stack.push(item + "");
            } else {
                if (!stack.isEmpty()) {
                    count++;
                    stack.pop();
                }
            }

        }
        return count;

    }

    //105.从前序遍历与中序遍历序列构造二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 1 && inorder.length == 1) return new TreeNode(preorder[0]);
        /*

            前序，中序，后序遍历，这三种遍历指的是遍历【根节点】的时机
            如：前序遍历的顺序为：根节点，左子树，右子树
             例如有：   3
                   1      2  我们采用前序遍历的结果是：3，1, 2。可见这个【前】指的是根节点在遍历的最前面

            现在题目给了我们前序遍历序列：preorder:[3,9,20,15,7]
                           中序遍历序列：inorder:[9,3,15,20,7]
                    让我们根据这两个序列来构造二叉树。

              第一步：根据前序遍历序列我们可以确定【根节点】为3
              第二步：再看中序遍历中【根节点3】前面只有一个元素，表示该二叉树根节点的左子树个数为1，即9
               就是这个样子    3
                         9
                剩下的节点都是存在于【根节点3】的右子树
              第三步：再根据前序遍历中9后面为20可以确定【根节点3】的右子树根节点为20，并且其左子树为15，右子树为7

                   那么这棵树就是：             3
                                        9       20
                                            15      7
         */


        //创建一个哈希表，用于记录中序序列中元素的下标
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }

        return buildTree(preorder, 0, preorder.length - 1, map, 0, inorder.length - 1);

    }

    private TreeNode buildTree(int[] preorder, int preLeft, int preRight, HashMap<Integer, Integer> map
            , int inLeft, int inRight) {
        if (preLeft > preRight || inLeft > inRight) {
            return null;
        }

        //构建根节点
        int rootValue = preorder[preLeft];
        TreeNode root = new TreeNode(rootValue);

        //拿到根节点在中序序列中的下标
        Integer pIndex = map.get(rootValue);

        root.left = buildTree(preorder, preLeft + 1, pIndex - inLeft + preLeft, map,
                inLeft, pIndex - 1);

        root.right = buildTree(preorder, pIndex - inLeft + preLeft + 1, preRight, map,
                pIndex + 1, inRight);

        return root;

    }

    //15.三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length < 3) return null;

        ArrayList<List<Integer>> res = new ArrayList<>();

        //对数组进行排序
        Arrays.sort(nums);

        //双指针开始解决问题
        int len = nums.length;

        for (int i = 0; i < len; i++) {

            if (nums[i] > 0) return res;//例如：-4，-1，-1,0,1,2 现在i为3，后面的是1 2（升序），那么就不会存在符合条件的元组
            if (i > 0 && nums[i - 1] == nums[i]) continue;//若符合这个条件，表示此时i对应的元素已经【当过cur了】，不要重复元组

            int cur = nums[i];

            int left = i + 1, right = len - 1;

            while (left < right) {
                int temp = cur + nums[left] + nums[right];

                if (temp == 0) {
                    //满足条件。将这个元组加入集合
                    res.add(Arrays.asList(cur, nums[left], nums[right]));
                    //进行判断，防止出现重复元组
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;

                    left++;
                    right--;

                } else if (temp < 0) {
                    left++;
                } else {
                    right--;
                }


            }


        }

        return res;
    }

    //844.比较含退格的字符串
    public boolean backspaceCompare(String s, String t) {
        if (s == null || t == null) return true;

        //双指针
        int pOne = s.length() - 1;
        int pTwo = t.length() - 1;

        //定义Skip，记录#的数量
        int skipS = 0;
        int skipT = 0;

        while (pOne >= 0 || pTwo >= 0) {

            while (pOne >= 0) {
                if (s.charAt(pOne) == '#') {
                    skipS++;
                    pOne--;
                } else if (skipS > 0) {
                    skipS--;
                    pOne--;
                } else {
                    break;
                }

            }

            while (pTwo >= 0) {
                if (t.charAt(pTwo) == '#') {
                    skipT++;
                    pTwo--;
                } else if (skipT > 0) {
                    skipT--;
                    pTwo--;
                } else {
                    break;
                }

            }

            if (pOne >= 0 && pTwo >= 0) {
                if (s.charAt(pOne) != t.charAt(pTwo)) {
                    return false;
                }
            } else {
                if (pOne >= 0 || pTwo >= 0) {
                    return false;
                }
            }

            pOne--;
            pTwo--;


        }


        return true;
    }

    //去除掉“#”和“#”之前应该去掉的字符，然后比较剩下来的
    public boolean backspaceCompare2(String s, String t) {
        if (s == null && t == null) return true;
        return buildString(s).equals(buildString(t));
    }

    private String buildString(String str) {
        StringBuilder builder = new StringBuilder();

        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '#') {
                if (builder.length() == 0) {
                    continue;
                } else {
                    builder.deleteCharAt(builder.length() - 1);
                }
            } else {
                builder.append(str.charAt(i));
            }
        }

        return builder.toString();
    }


    //986.区间列表的交集
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        ArrayList<int[]> res = new ArrayList<>();
        int i = 0, j = 0;

        while (i < firstList.length && j < secondList.length) {
            int max = Math.max(firstList[i][0], secondList[j][0]);
            int min = Math.min(firstList[i][1], secondList[j][1]);

            if (max <= min) {
                res.add(new int[]{max, min});
            }

            if (firstList[i][1] > secondList[j][1]) {
                j++;
            } else {
                i++;
            }

        }
        return res.toArray(new int[0][0]);

    }


    //11.盛水最多的容器
    public int maxArea(int[] height) {
        if (height == null) {
            return 0;
        }

        //水桶的容量取决于它的板，故可以得到公式：S=Min(H[i],H[j])*(j-i)【宽成高】


        //双指针
        int left = 0, right = height.length - 1, max = 0;

        while (left < right) {

            int min = Math.min(height[left], height[right]);//拿到短板
            max = Math.max(max, min * (right - left));

            //判断拿一个是短板以及哪一边该向内收缩
            if (min == height[left]) {//若【左】边小，则从左边向内收缩
                left++;
            } else {
                //若【右】边小，则从右边向内收缩
                right--;
            }

        }

        return max;

    }
    public int maxArea2(int[] height) {
        if (height == null) return 0;

        int left = 0, right = height.length - 1, max = 0;

        while (left < right) {
            max = height[left] < height[right] ?
                    Math.max(max, (right - left) * height[left++]) ://左为短边【left++】表示向左收缩
                    Math.max(max, (right - left) * height[right--]);

        }

        return max;

    }


    public static void main(String[] args) {
        t20211027 t20211027 = new t20211027();


        String str = "()())()";

        HashSet<String> hashSet = new HashSet<>();
        hashSet.add(str);

        System.out.println(t20211027.maxArea2(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}));


    }


}

class User {
    private String name;
    private Integer age;
    private Integer salary;

    public User() {
    }

    public User(String name, Integer age, Integer salary) {
        this.name = name;
        this.age = age;
        this.salary = salary;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Integer getAge() {
        return age;
    }

    public void setAge(Integer age) {
        this.age = age;
    }

    public Integer getSalary() {
        return salary;
    }

    public void setSalary(Integer salary) {
        this.salary = salary;
    }

    @Override
    public String toString() {
        return "User{" +
                "name='" + name + '\'' +
                ", age=" + age +
                ", salary=" + salary +
                '}';
    }
}